package com.zhouyong.leetcode.链表中倒数第k个节点22;

import com.zhouyong.leetcode.ListNode;

/**
 * @Author 99
 * @Date 2022/10/1 14:16
 * @Version 1.0
 */
public class Test {

    // 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
    // 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

    // 给定一个链表: 1->2->3->4->5, 和 k = 2.
    // 返回链表 4->5.
    public static void main(String[] args) {
        ListNode node = new ListNode(1);
        System.out.println(getKthFromEnd(node, 1));
    }

    public static ListNode getKthFromEnd(ListNode head, int k) {

        // 顺序查询
//        int count = 0, index = 1;
//        ListNode init = head;
//        while (head != null) {
//            count++;
//            head = head.next;
//        }
//        if (k == count) {
//            return init;
//        }
//        int newCount = count - k;
//        while (init != null) {
//            if (index == newCount) {
//                return init.next;
//            }
//            init = init.next;
//            index++;
//        }
//        return null;

        // 快慢指针
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && k > 0) {
            fast = fast.next;
            k--;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        return slow;
    }
}
